import java.util.HashMap;
import java.util.Map;

/**
 * 337. 打家劫舍 III
 */
public class Solution_337 {
    /**
     * 官方题解：动态规划
     * 
     * 问题简化：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），
     * 问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
     */
    // f(o) 表示选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和
    Map<TreeNode, Integer> f = new HashMap<>();
    // g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和
    Map<TreeNode, Integer> g = new HashMap<>();

    /**
     * 当 o 被选中时，o 的左右孩子都不能被选中，
     * 故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，
     * 即 f(o) = g(l) + g(r)。
     * <p>
     * 当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。
     * 对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。
     * 故 g(o) = max{f(l),g(l)} + max{f(r),g(r)}。
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0))
                + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }
}
